{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.7.4-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Language modeling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import reduce, partial\n",
    "\n",
    "START, END = \"<start{}>\", \"<end>\"\n",
    "\n",
    "\n",
    "def gram_key(words: list, i: int, n: int) -> str:\n",
    "    keys = []\n",
    "    if i < n - 1:\n",
    "        for j in range(n - i - 1):\n",
    "            keys.append(START.format(j + i+1))\n",
    "    for j in range(max(0, i + 1 - n), i):\n",
    "        keys.append(words[j])\n",
    "    return '_'.join(keys)\n",
    "\n",
    "\n",
    "def ngram_counting(text: str, n: int):\n",
    "    # <w_i-1, w_i-2> : {w_i: c}\n",
    "    ngram_counts = {}\n",
    "    words = train_text.lower().split()\n",
    "    for i in range(len(words) + 1):\n",
    "        key = gram_key(words, i, n)\n",
    "        if i != len(words):\n",
    "            word = words[i]\n",
    "        else:\n",
    "            word = END\n",
    "        if key in ngram_counts:\n",
    "            counts = ngram_counts[key]\n",
    "            if word in counts:\n",
    "                counts[word] += 1\n",
    "            else:\n",
    "                counts[word] = 1\n",
    "        else:\n",
    "            ngram_counts[key] = {word: 1}\n",
    "    unigrams = set(words)\n",
    "    return (ngram_counts, unigrams)\n",
    "\n",
    "\n",
    "def p(words: list, i: int, ngram_counts: dict, v: int, n: int, laplacian_smooth: bool = True):\n",
    "    key = gram_key(words, i, n)\n",
    "    if key in ngram_counts:\n",
    "        counts = ngram_counts[key]\n",
    "        if i < len(words):\n",
    "            word = words[i]\n",
    "        else:\n",
    "            word = END\n",
    "        if word in counts:\n",
    "            a = counts[word]\n",
    "        else:\n",
    "            a = 0\n",
    "        b = sum([v for k, v in counts.items()])\n",
    "    else:\n",
    "        a = 0\n",
    "        b = 0\n",
    "    if laplacian_smooth:\n",
    "        return (a + 1) / (b + v)\n",
    "    else:\n",
    "        if b == 0:\n",
    "            print(\"warn: i = {}, key <{}> = 0\".format(i, key))\n",
    "        return a / b\n",
    "\n",
    "\n",
    "def perplexity(ngram_counts, unigrams: dict, test_text: str, n: int, laplacian_smooth: bool = True):\n",
    "    words = test_text.lower().split()\n",
    "    N = len(words)\n",
    "    v = len(unigrams) + 1\n",
    "    print(\"V = {}, N = {}\".format(v, N))\n",
    "    f = partial(p, words=words, ngram_counts=ngram_counts,\n",
    "                v=v, laplacian_smooth=laplacian_smooth, n=n)\n",
    "    prod = reduce(lambda x, y: x*y, [f(i=i) for i in range(len(words) + 1)])\n",
    "    if prod == 0.0:\n",
    "        return float(\"inf\")\n",
    "    else:\n",
    "        return prod ** (- 1.0 / N)\n",
    "\n",
    "\n",
    "def sentence_prob(ngram_counts: dict, test_text: str, n: int):\n",
    "    words = test_text.lower().split()\n",
    "    N = len(words)\n",
    "    f = partial(p, words=words, ngram_counts=ngram_counts,\n",
    "                v=0, laplacian_smooth=False, n=n)\n",
    "    prod = reduce(lambda x, y: x*y, [f(i=i) for i in range(N + 1)])\n",
    "    return prod"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Q2\n",
    "\n",
    "Consider the bigram language model trained on the sentence:\n",
    "\n",
    "This is the cow with the crumpled horn that tossed the dog that worried the cat that killed the rat that ate the malt that lay in the house that Jack built.\n",
    "\n",
    "Find the probability of the sentence:\n",
    "\n",
    "This is the rat that worried the dog that Jack built."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "Q2: sentence prob 0.0005668934240362811\ntrain: ngram counts =>  {'<start1>': {'this': 1}, 'this': {'is': 1}, 'is': {'the': 1}, 'the': {'cow': 1, 'crumpled': 1, 'dog': 1, 'cat': 1, 'rat': 1, 'malt': 1, 'house': 1}, 'cow': {'with': 1}, 'with': {'the': 1}, 'crumpled': {'horn': 1}, 'horn': {'that': 1}, 'that': {'tossed': 1, 'worried': 1, 'killed': 1, 'ate': 1, 'lay': 1, 'jack': 1}, 'tossed': {'the': 1}, 'dog': {'that': 1}, 'worried': {'the': 1}, 'cat': {'that': 1}, 'killed': {'the': 1}, 'rat': {'that': 1}, 'ate': {'the': 1}, 'malt': {'that': 1}, 'lay': {'in': 1}, 'in': {'the': 1}, 'house': {'that': 1}, 'jack': {'built': 1}, 'built': {'<end>': 1}}\ntrain: unigrams =>  {'dog', 'the', 'lay', 'in', 'rat', 'with', 'crumpled', 'cat', 'tossed', 'is', 'house', 'ate', 'cow', 'malt', 'that', 'killed', 'horn', 'worried', 'this', 'jack', 'built'}\n"
    }
   ],
   "source": [
    "train_text = \"This is the cow with the crumpled horn that tossed the dog that worried the cat that killed the rat that ate the malt that lay in the house that Jack built\"\n",
    "ngram_counts, unigrams = ngram_counting(train_text, 2)\n",
    "\n",
    "test_text = \"This is the rat that worried the dog that Jack built\"\n",
    "try:\n",
    "    v = sentence_prob(ngram_counts, test_text, 2)\n",
    "    print(\"Q2: sentence prob\", v)\n",
    "except ZeroDivisionError:\n",
    "    print(\"Q2: sentence prob 0/0\")\n",
    "print(\"train: ngram counts => \", ngram_counts)\n",
    "print(\"train: unigrams => \", unigrams)"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Q3\n",
    "\n",
    "Consider the trigram language model trained on the sentence:\n",
    "\n",
    "This is the cat that killed the rat that ate the malt that lay in the house that Jack built.\n",
    "\n",
    "Find the perplexity of this model on the test sentence:\n",
    "\n",
    "This is the house that Jack built."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "V = 13, N = 7\nQ3:  inf\ntrain: ngram counts =>  {'<start1>_<start2>': {'this': 1}, '<start2>_this': {'is': 1}, 'this_is': {'the': 1}, 'is_the': {'rat': 1}, 'the_rat': {'that': 1}, 'rat_that': {'ate': 1}, 'that_ate': {'the': 1}, 'ate_the': {'malt': 1}, 'the_malt': {'that': 1}, 'malt_that': {'lay': 1}, 'that_lay': {'in': 1}, 'lay_in': {'the': 1}, 'in_the': {'house': 1}, 'the_house': {'that': 1}, 'house_that': {'jack': 1}, 'that_jack': {'built': 1}, 'jack_built': {'<end>': 1}}\ntrain: unigrams =>  {'that', 'house', 'is', 'the', 'lay', 'in', 'rat', 'ate', 'this', 'jack', 'malt', 'built'}\n"
    }
   ],
   "source": [
    "train_text = \"This is the rat that ate the malt that lay in the house that Jack built\"\n",
    "test_text = \"This is the house that Jack built\"\n",
    "\n",
    "ngram_counts, unigrams = ngram_counting(train_text, 3)\n",
    "v = perplexity(ngram_counts, unigrams, test_text, 3, laplacian_smooth=False)\n",
    "print(\"Q3: \", v)\n",
    "print(\"train: ngram counts => \", ngram_counts)\n",
    "print(\"train: unigrams => \", unigrams)"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Q4\n",
    "Apply add-one smoothing to the trigram language model trained on the sentence:\n",
    "\n",
    "This is the rat that ate the malt that lay in the house that Jack built.\n",
    "\n",
    "Find the perplexity of this smoothed model on the test sentence:\n",
    "\n",
    "This is the house that Jack built.\n",
    "\n",
    "Write the answer with precision of 3 digits after the decimal point."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "V = 13, N = 7\nQ4: 10.205413747033985\ntrain: ngram counts =>  {'<start1>_<start2>': {'this': 1}, '<start2>_this': {'is': 1}, 'this_is': {'the': 1}, 'is_the': {'rat': 1}, 'the_rat': {'that': 1}, 'rat_that': {'ate': 1}, 'that_ate': {'the': 1}, 'ate_the': {'malt': 1}, 'the_malt': {'that': 1}, 'malt_that': {'lay': 1}, 'that_lay': {'in': 1}, 'lay_in': {'the': 1}, 'in_the': {'house': 1}, 'the_house': {'that': 1}, 'house_that': {'jack': 1}, 'that_jack': {'built': 1}, 'jack_built': {'<end>': 1}}\ntrain: unigrams =>  {'that', 'house', 'is', 'the', 'lay', 'in', 'rat', 'ate', 'this', 'jack', 'malt', 'built'}\n"
    }
   ],
   "source": [
    "train_text = \"This is the rat that ate the malt that lay in the house that Jack built\"\n",
    "ngram_counts, unigrams = ngram_counting(train_text, 3)\n",
    "\n",
    "test_text = \"This is the house that Jack built\"\n",
    "v = perplexity(ngram_counts, unigrams, test_text, 3, laplacian_smooth=True)\n",
    "print(\"Q4:\", v)\n",
    "print(\"train: ngram counts => \", ngram_counts)\n",
    "print(\"train: unigrams => \", unigrams)"
   ]
  }
 ]
}